/*************************************************************************
	> File Name: 002.BinarySearchTree.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 三  9/ 8 18:45:04 2021
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*
 * 二叉搜索树结点定义
 */
typedef struct Node {
    int val;
    struct Node *lchild;
    struct Node *rchild;
} Node;

/*
 * 树的结构定义
 */
typedef struct Tree {
    Node *root;
    int cnt;
} Tree;

/*
 * 结点初始化
 */
Node *init_node(int val) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->val = val;
    node->lchild = NULL;
    node->rchild = NULL;
    return node;
}

/*
 * 树的初始化
 */
Tree *init_tree() {
    Tree *tree = (Tree *)malloc(sizeof(Tree));
    tree->root = NULL;
    tree->cnt = 0;
    return tree;
}

/*
 * 销毁结点
 */
void destroy_node(Node *node) {
    if (node == NULL) return ;
    destroy_node(node->lchild);
    destroy_node(node->rchild);
    free(node);
    return ;
}

/*
 * 销毁树
 */
void destroy_tree(Tree *tree) {
    if (tree == NULL) return ;
    destroy_node(tree->root);
    free(tree);
    return ;
}

/*
 * 结点的插入
 */
Node *insert_node(Node *root, int val, int *flag) { 
    if (root == NULL) {
        *flag = 1;
        return init_node(val);
    }
    if (root->val == val) return root; //待插入的值与根节点值相等，不做任何插入操作
    if (val < root->val)  //待插入的值比根节点值小，则要插在左子树上
        root->lchild = insert_node(root->lchild, val, flag);
    else //待插入的值比根节点值大，则要插在右子树上
        root->rchild = insert_node(root->rchild, val, flag);
    return root;
}

/*
 * 插入操作
 */
void insert(Tree *tree, int val) {
    int flag = 0;
    tree->root = insert_node(tree->root, val, &flag);
    tree->cnt += flag; //如果flag = 1，表示插入成功，更新节点数
    return ;
}

/*
 * 先序遍历
 */
void pre_order_node(Node *node) {
    if (node == NULL) return ;
    printf("%d ", node->val);
    pre_order_node(node->lchild);
    pre_order_node(node->rchild);
    return ;
}


void pre_order(Tree *tree) {
    if (tree == NULL) return ;
    printf("pre_order: ");
    pre_order_node(tree->root);
    printf("\n");
    return;
}

/*
 * 中序遍历
 */
void in_order_node(Node *node) {
    if (node == NULL) return ;
    in_order_node(node->lchild);
    printf("%d ", node->val);
    in_order_node(node->rchild);
    return ;
}


void in_order(Tree *tree) {
    if (tree == NULL) return ;
    printf("in_order: ");
    in_order_node(tree->root);
    printf("\n");
    return;
}

/*
 * 后序遍历
 */
void post_order_node(Node *node) {
    if (node == NULL) return ;
    post_order_node(node->lchild);
    post_order_node(node->rchild);
    printf("%d ", node->val);
    return ;
}


void post_order(Tree *tree) {
    if (tree == NULL) return ;
    printf("post_order: ");
    post_order_node(tree->root);
    printf("\n");
    return;
}

/*
 * 节点值的打印
 */
void output_node(Node *node) {
    if (node == NULL) return ;
    printf("%d", node->val);
    if (node->lchild == NULL && node->rchild == NULL) return ;
    printf("(");
    output_node(node->lchild);
    printf(",");
    output_node(node->rchild);
    printf(")");
    return ;
}

/*
 * 二叉树转广义表
 */
void output(Tree *tree) {
    if (tree == NULL) return ;
    printf("tree(%d) : ", tree->cnt);
    output_node(tree->root);
    printf("\n");
    return ;
}


int main() {
    srand(time(0));
    Tree *tree = init_tree();
    #define max_op 10
    for (int i = 0; i < max_op; i++) {
        int val = rand() % 100;
        insert(tree, val);
        output(tree);
    }
    pre_order(tree);
    in_order(tree);
    post_order(tree);
    #undef max_op
    destroy_tree(tree);
    
    return 0;
}

/* 测试结果：
 * tree(2) : 7(,62)
 * tree(3) : 7(,62(48,))
 * tree(4) : 7(,62(48(19,),))
 * tree(5) : 7(,62(48(19,),68))
 * tree(6) : 7(,62(48(19,),68(,90)))
 * tree(7) : 7(6,62(48(19,),68(,90)))
 * tree(8) : 7(6,62(48(19(17,),),68(,90)))
 * tree(9) : 7(6,62(48(19(17,),),68(,90(71,))))
 * tree(10) : 7(6,62(48(19(17,),53),68(,90(71,))))
 * pre_order: 7 6 62 48 19 17 53 68 90 71
 * in_order: 6 7 17 19 48 53 62 68 71 90
 * post_order: 6 17 19 53 48 71 90 68 62 7
 * 
 */
